package leetcode;

import java.util.ArrayList;
import java.util.Arrays;

public class LeetCodeMain64 {
    public int balancedStringSplit(String s) {
        int count=0;
        int balance=0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)=='R'){
                balance++;
            }if (s.charAt(i)=='L'){
                balance--;
            }if (balance==0){
                count++;
            }
        }
        return count;
    }
    public int numDistinct (String S, String T) {
        // write code here
        int length1=S.length();
        int length2=T.length();
        if (length1<length2){
            return 0;
        }
        int[][] dp=new int[length1+1][length2+1];
        for (int i = 0; i <= length1; i++) {
            dp[i][0]=1;
        }

        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                if (S.charAt(i-1)==T.charAt(j-1)){
                    dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
                }else {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[length1][length2];
    }
    public int minDistance2 (String word1, String word2) {
        // write code here
        int length1=word1.length();
        int length2=word2.length();
        int[][] dp=new int[length1+1][length2+1];
        for (int i = 1; i <= length1; i++) {
            dp[i][0]=i;
        }
        for (int i = 1; i <= length2; i++) {
            dp[0][i]=i;
        }
        for (int i = 1; i <= length1; i++) {
            for (int j = 1; j <= length2; j++) {
                if (word1.charAt(i-1)==word2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else {
                    dp[i][j]=Math.min(dp[i-1][j-1],Math.min(dp[i-1][j],dp[i][j-1]))+1;
                }
            }
        }
        return dp[length1][length2];
    }
    public int minCut (String s) {
        // write code here
        int length=s.length();
        if (length==0){
            return 0;
        }
        int[] dp=new int[length+1];
        for (int i = 0; i <= length; i++) {
            dp[i]=i-1;
        }
        for (int i = 1; i <= length; i++) {
            for (int j = 0; j < i; j++) {
                if (!is(s,j,i-1)){
                    dp[i]=Math.min(dp[i],dp[j]+1);
                }
            }
        }
        return dp[length];
    }
    public boolean is(String s,int start,int end){
        while (start<=end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }
    public int backPackII(int m, int[] A, int[] V) {
        int[] dp=new int[m+1];
        int length=A.length;
        for (int i = 1; i <= length; i++) {
            for (int j = m; j >0; j--) {
                if (j>=A[i-1]){
                    dp[j]=Math.max(dp[j],dp[j-A[i]]+V[i]);
                }
            }
        }
        return dp[m];
    }
        public int backPackII1(int m, int[] A, int[] V) {
        // write your code here
        int length=A.length;
        int[][] dp=new int[length][m+1];
        for (int i = 0; i <= m; i++) {
            if (A[0]>i){
                dp[0][i]=0;
            }else {
                dp[0][i]=V[0];
            }
        }
        for (int i = 1; i < length; i++) {
            for (int j = 1; j <= m; j++) {
                if (A[i]>j){
                    dp[i][j]=dp[i-1][j];
                }else {
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-A[i]]+V[i]);
                }
            }
        }
        return dp[length-1][m];
    }
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        int length1=triangle.size();
        int length2=triangle.get(length1-1).size();
        int[][] dp=new int[length1][length2];
        for (int i = 0; i < length2; i++) {
            dp[length1-1][i]=triangle.get(length1-1).get(i);
        }
        for (int i = length1-2; i >=0 ; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }
    public int uniquePaths (int m, int n) {
        // write code here
        int[][] dp=new int[m][n];
        dp[0][0]=1;
        for (int i = 1; i < m; i++) {
            dp[i][0]=1;
        }
        for (int i = 1; i < n; i++) {
            dp[0][i]=1;
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }
    public int minPathSum (int[][] grid) {
        // write code here
        for (int i = 1; i < grid.length; i++) {
            grid[i][0]+=grid[i-1][0];
        }
        for (int i = 1; i < grid[0].length; i++) {
            grid[0][i]+=grid[0][i-1];
        }
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                grid[i][j]+=Math.min(grid[i-1][j],grid[i][j-1]);
            }
        }
        return grid[grid.length-1][grid[0].length-1];
    }
}
